package 力扣.排序.合并排序;

public class 寻找两个正序数组的中位数4 {
    /**
     * 垃圾版：仅仅作为合并排序中的合并练习
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null && nums2 == null || nums1.length == 0 && nums2.length == 0){
            return 0;
        }
        int n1 = nums1.length;
        int n2 = nums2.length;
        int N = n1 + n2;
        int[] t = new int[N];
        int i = 0,j = 0,to = 0;
        while (i < n1 || j < n2){
            if (j >= n2 || (i < n1 && nums1[i] < nums2[j])){
                t[to++] = nums1[i++];
            }else {
                t[to++] = nums2[j++];
            }
        }
        int mid = N >> 1;
        if ((N & 0x01) == 1){
            return  t[mid];
        }else {
            return (t[mid - 1] + t[mid]) / 2.0;
        }
    }

    /**
     *
     * @param A
     * @param B
     * @return
     */
    double findMedianSortedArrays2(int[] A, int[] B) {
        final int len = A.length + B.length;
        final int alen = A.length, blen = B.length;
        int i = 0, j = 0;
        // 如果两个数组的总长度为0
        //那么不用再找了，肯定是没有中位数的，这里直接返回一个0
        if (len == 0) {
            return 0;
        }
        // 总长度为偶数的情况：
        // 如果有4个数，那么当扔掉1个数之后
        // 接下来需要合并的两个数排[2,3]就是中位数
        // 总长度为奇数的情况：
        // 比如如果有5个数，那么当合并掉2个数之后
        // 接下来的那个排[3]位的就是中位数。
        // 所以这里k表示：要扔掉的数的个数
        int k = (len - 1) >> 1;
        while (k > 0) {
            // 我们需要比较A[p]与B[p]
            // 只不过当数组的起始位置是i和j的时候。
            // 比较的元素就变成 A[i+p], B[j+p]
            final int p = (k - 1) >> 1;//先扔掉一半
            // 这时直接比较A[i + p]和B[j+p]来决定谁可以被扔掉掉
            // 注意这里扔掉的时候，只需要前移p + 1即可。
            if (j + p >= blen || (i + p < alen && A[i + p] < B[j + p])) {
                i += p + 1;
            } else {
                j += p + 1;
            }
            k -= p + 1;//p是数组下标，所以要多减一
        }
        // 把排在前面的数取出来
        double front =
                (j >= blen || (i < alen && A[i] < B[j])) ? A[i++] : B[j++];
        // 如果总长度为奇数，那么这个时候，front就是我们要找的中位数
        if ((len & 1) == 1) {
            return front;
        }
        // 此时总的数目为偶数，那么需要再取一个数，求平均值。
        double back =
                (j >= blen || (i < alen && A[i] < B[j])) ? A[i] : B[j];
        return (front + back) / 2.0;
    }

/*//从两个有序数组中寻找中位数，那么就要从先扔掉一半的数字。从两个数组
    double findMedianSortedArrays3(int[] A, int[] B) {
        int len1 = A.length;
        int len2 = B.length;
        int len = len1 + len2;
        if (len == 0){
            return 0;
        }
        //中位数：先扔掉一半的数字即可

    }*/
}
